public class Main {

    public static int solution(int n, int[] a, int[] b) {
        final int mod = (int) 1e9 + 7;

        // 扩展数组，索引从1开始（Java中我们通过偏移处理）
        int[] aExtended = new int[n + 1];
        int[] bExtended = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            aExtended[i] = a[i - 1] % 3;
            bExtended[i] = b[i - 1] % 3;
        }

        // dp[i][j] 表示前 i 个位置，使得总和模3等于 j 的方案数
        int[][] f = new int[n + 1][3];
        f[0][0] = 1; // 初始状态：0个元素时和为0的方案数为1

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 3; j++) {
                int prev1 = (j + 3 - aExtended[i]) % 3;
                int prev2 = (j + 3 - bExtended[i]) % 3;
                f[i][j] = (f[i - 1][prev1] + f[i - 1][prev2]) % mod;
            }
        }

        return f[n][0];
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution(3, new int[]{1, 2, 3}, new int[]{2, 3, 2}) == 3);
        System.out.println(solution(4, new int[]{3, 1, 2, 4}, new int[]{1, 2, 3, 1}) == 6);
        System.out.println(solution(5, new int[]{1, 2, 3, 4, 5}, new int[]{1, 2, 3, 4, 5}) == 32);
    }
}